package leetcode.stack_queue;

import java.util.Arrays;
import java.util.LinkedList;

public class Lc503 {


    public int[] nextGreaterElements(int[] nums) {

        LinkedList<Integer> dq = new LinkedList<>(); //存储nums的下标,防止nums中数字有重复，同一个数不能同时进队两次
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1); // 非最大元素可能会重复进队，ans初始化-1，对于已经找到更大元素的值，重复进度后不再更新ans值，否则会是错误的值
        int cnt = 0; // 找到更大元素的个数，当cnt==nums.length时表明所有元素的下一个更大值均已找到，可以结束了
        dq.addLast(0);
        for (int i = 1; ; i++) {
            if (i >= nums.length) {
                if (cnt == nums.length)  break;
                i = i % nums.length;
            }
            if (dq.isEmpty()  ) {
                dq.addLast(i);
            } else {
                //先判断当前nums[i]是否已经在队列中了
                if (dq.getFirst() == i) { //已经在队列中了，说明找了一圈没找到nums[i]的更大值，nums[i]就是最大的值，可以把队列清空了，然后结束
                    ans[dq.getFirst()] = -1;
                    cnt++;
                    dq.removeFirst();
                    while (!dq.isEmpty() && nums[i] > nums[dq.getLast()]) {
                        if (ans[dq.getLast()] == -1) { //对于之前已经找到更大元素的值不再更新ans
                            ans[dq.getLast()] = nums[i];
                            cnt++;
                        }
                        dq.removeLast();
                    }
                    break;
                } else {//没有在队列中
                    if (nums[i] <= nums[dq.getLast()]) {// 当前元素比队位元素小，直接进队
                        dq.addLast(i);
                    } else {//当前元素大于队尾元素，队尾弹出，更新他的更大值
                        while (!dq.isEmpty() && nums[i] > nums[dq.getLast()]) {
                            ans[dq.getLast()] = nums[i];
                            cnt++;
                            dq.removeLast();
                        }
                        dq.addLast(i);
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {

        Lc503 lc503 = new Lc503();
        int[] nums = new int[]{1,2,3,4,3};
        int [] ans = lc503.nextGreaterElements(nums);
        for (int i = 0; i < ans.length; i++) {
            System.out.println(ans[i]);
        }


//        LinkedList<Integer> dq = new LinkedList<>();
//
//        dq.addLast(1);
//        dq.addLast(2);
//        dq.addLast(3);
//        System.out.println(dq.getFirst());
//        System.out.println(dq.getLast());
//        System.out.println(dq.removeFirst());
//        System.out.println(dq.removeLast());

    }



}
